package demo.practice.dp;

import java.util.HashMap;
import java.util.Map;

public class P560_2 {

    public static void main(String[] args) {
        P560_2 p560_2 = new P560_2();
        p560_2.subarraySum(new int[]{1, 2, 1, 2, 1}, 3);
    }

    public int subarraySum(int[] nums, int k) {
        int[] store = new int[nums.length + 1];
        for (int i = 1; i < store.length; i++) {
            store[i] = store[i - 1] + nums[i - 1];
        }

        Map<Integer, Integer> map = new HashMap<>();
        int c = 0;  //store[i]- store[j] 代表 i~j之间的和
        for (int i = 1; i < store.length; i++) {
            if (store[i] == k) {
                c++;
            }
            if (map.containsKey(store[i])) {
                c += map.get(store[i]);
            }
            if (!map.containsKey(store[i] + k)) {
                map.put(store[i] + k, 0);
            }
            map.put(store[i] + k, map.get(store[i] + k) + 1);
        }
        return c;
    }
}
